package com.yhy;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * describe: 由顶点和边组成的图
 *
 * @author helloworldyu
 * @data 2017/11/14
 */
public class SparseGraph implements IGraph{
	private HashMap<Vertex,ArrayList<Vertex>> vertexTable=new HashMap<>();
	private boolean dircted;

	SparseGraph( boolean dircted ){
		this.dircted = dircted;
	}

	@Override
	public boolean isDirected() {
		return dircted;
	}

	@Override
	public boolean addVertex(Vertex vertex) {
		Set<Vertex> vertices = vertexTable.keySet();

		for ( Vertex vertex1 : vertices ){
			if( vertex1.getId()==vertex.getId() ){
				return false;
			}
		}
		vertexTable.put(vertex,new ArrayList<>());
		return true;
	}

	@Override
	public void connect(Vertex a, Vertex b) {
		//=========判断是否在图中=========
		Vertex inGraph = findInGraph(a);
		if( null == inGraph ){
			throw new RuntimeException("a 不在图中");
		}

		Vertex inGraph1 = findInGraph(b);
		if( null == inGraph1 ){
			throw new RuntimeException("b 不在图中");
		}

		//=========是否是自环边=============
		if( inGraph.equals(inGraph1) ){
			return;
		}
		//=========是否是无向图=============
		ArrayList<Vertex> adj = getAdj(inGraph);
		adj.add(inGraph1);
		if( !dircted ){
			ArrayList<Vertex> adj1 = getAdj(inGraph1);
			adj1.add(inGraph);
		}
	}

	@Override
	public boolean hasEdge(Vertex a, Vertex b) {
		//=========判断是否在图中=========
		Set<Vertex> vertices = vertexTable.keySet();
		if( vertices.contains(a) && vertices.contains(b) ){
			ArrayList<Vertex> vertices1 = vertexTable.get(a);
			for( Vertex vertex : vertices1 ){
				if( vertex== b ){
					return true;
				}
			}
			return false;
		}else {
			throw new RuntimeException("不在图中的点");
		}
	}

	@Override
	public Set<Vertex> getVertexs() {
		return vertexTable.keySet();
	}

	@Override
	public ArrayList<Vertex> getAdj(Vertex vertex) {
		return vertexTable.get(vertex);
	}

	@Override
	public Vertex findInGraph(Vertex vertex) {
		Set<Vertex> vertices = vertexTable.keySet();

		for ( Vertex ver : vertices ){
			if( ver.getId()==vertex.getId() ){
				return ver;
			}
		}
		return null;
	}

	@Override
	public void show() {
		Set<Map.Entry<Vertex, ArrayList<Vertex>>> entries = vertexTable.entrySet();
		for( Map.Entry<Vertex,ArrayList<Vertex>> entry : entries ){
			System.out.println(entry.toString());
		}
	}
}